﻿// 0810train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

/*
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3
 */
int solve01(vector<int>&nums, int target)
{
    //sum=positive+negative
    //target=positive-negative
    if (nums.size()==1)
    {
        if (nums[0] == abs(target)) return 1;
        return 0;
    }

    int sum = 0;
    for (auto&num:nums)
    {
        sum += num;
    }

    if (sum < target) return 0;

    if ((sum + target) % 2 != 0)
    {
        return 0;
    }

    int positive = (sum + target) / 2;

    if (positive < 0) return 0;

    //dp[i][w]前i个数中，凑齐w的种数
    int dp_size = nums.size() + 1;
    int sum_size = positive + 1;
    vector<int>sum_vec(sum_size, 0);
    vector<vector<int>>dynamic_grid(dp_size, sum_vec);

    dynamic_grid[0][0] = 1;

    for (int i=1; i<dp_size; i++)
    {
        for (int w=0; w<sum_size; w++)
        {
            int curr_w = nums[i - 1];
            if (w< curr_w)
            {
                //curr_w不可取，只能继承
                dynamic_grid[i][w] = dynamic_grid[i - 1][w];
            }
            else
            {
                //1同上，不取curr_w + 2取curr_w
                dynamic_grid[i][w] = dynamic_grid[i - 1][w] + dynamic_grid[i-1][w - curr_w];
            }

        }
    }

    //for (auto&mini_vec:dynamic_grid)
    //{
	   // for (auto&num:mini_vec)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}

    return dynamic_grid[dp_size - 1][positive];
    //solve01------
}


/*
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。
那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 */
int solve02(vector<int>&stones)
{
    //target==sum/2
    int sum = 0;
    for (auto&num:stones)
    {
        sum += num;
    }
    int target = sum / 2;

    int dp_size = stones.size()+1;
    int sum_size = target + 1;
    vector<int>sum_vec(sum_size, 0);
    vector<vector<int>>dynamic_grid(dp_size, sum_vec);
    //dp[i][w]的含义，前i个数总和不超过w的最大价值
    
    
    for (int i=1; i<dp_size; i++)
    {
        for (int w=0; w<sum_size; w++)
        {
            int curr_w = stones[i - 1];
            if (w<curr_w)
            {
	            //curr_w不可取
                dynamic_grid[i][w] = dynamic_grid[i - 1][w];
            }
            else
            {
                //取curr_w/不取curr_w
                int has_curr_w = dynamic_grid[i - 1][w - curr_w] + curr_w;
                dynamic_grid[i][w] = max(dynamic_grid[i - 1][w], has_curr_w);
            }

        }
    }

    //for (auto&mini_vec:dynamic_grid)
    //{
	   // for (auto&num:mini_vec)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}

    int max_half_sum = dynamic_grid[dp_size - 1][target];
    return abs(sum- 2*max_half_sum);
    //solve02
}

int lastStoneWeightII(vector<int>& stones) {

    // 在两块石头碰撞过程中，可以每次把大的石头划分到 A 部分，小的石头划分到 B 部分
    // 因此可以将数组分成 A 和 B 两个部分
    // A 部分的石头可以被部分留下
    // B 部分的石头全部被粉碎

    // 接下来就是需要思考到底哪些石头放入 A 部分，哪些石头放入 B 部分
    // 其中 A 部分的石头重量和是 sumA
    // 其中 B 部分的石头重量和是 sumB
    // 为了使得最后剩下的石头尽可能的小，那么总是会想去构造 { a , b } 这两个石头的差值尽可能的小
    // 于是问题就变成了：从 stones 中选择一些元素，总和不超过 sum / 2 的最大值

    // 先去计算总和
    int sum = accumulate(stones.begin(), stones.end(), 0);

    int target = sum / 2;

    // dp[i][j] 代表考虑前 i 个物品（数值），凑成总和不超过 j 的最大价值
    vector<vector<int>> dp(stones.size() + 1, vector<int>(target + 1));

    // 01 背包问题开始填充二维数组
    for (int i = 1; i <= stones.size(); i++) {

        for (int j = 0; j <= target; j++) {

            // 注意到 i 是从下标 1 开始访问的
            // 1、背包容量小于当前元素
            // 背包无法放入 stones[i - 1]
            if (j < stones[i - 1]) {

                dp[i][j] = dp[i - 1][j];

                // 2、背包容量大于等于当前元素
                // 背包可以放入 stones[i - 1]
            }
            else {

                // 不选：方案数为 dp[i - 1][j]
                // 选：方案数为 dp[i - 1][j - stones[i - 1]] + stones[i-1]
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }
    }

    for (auto& mini_vec : dp)
    {
        for (auto& num : mini_vec)
        {
            cout << num << ' ';
        }
        cout << '\n';
    }

    // 这两个部分最大值是 dp[stones.length][target]，剩余的部分就是剩下的石头
    return abs(sum - dp[stones.size()][target] - dp[stones.size()][target]);

}


int main()
{
	{
        //stones = [2,7,4,1,8,1] 1
        //stones = [31,26,33,21,40] 5
        vector<int>stones = { 31,26,33,21,40 };
        cout << solve02(stones);
        return 0;
	}

    //nums = [1, 1, 1, 1, 1], target = 3
    //nums = [1000] ,target=-1000
    //nums = [1, 1, 1, 1] target=-1000
    vector<int>nums = { 1, 1, 1, 1 };
    int target = -1000;
    cout << solve01(nums, target);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
